package Leetcode.数组字符串;

import java.util.Arrays;

/**
 * @ClassName K和数对的最大数目
 * @since: 2023/8/9 20:17
 * @auth: kirito
 * @description: 不要看题目 看解释 就行，题目讲的啥玩意儿。
 * 给你一个整数数组 nums 和一个整数 k 。
 *
 * 每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。
 *
 * 返回你可以对数组执行的最大操作数。
 * 示例 1：
 *
 * 输入：nums = [1,2,3,4], k = 5
 * 输出：2
 * 解释：开始时 nums = [1,2,3,4]：
 * - 移出 1 和 4 ，之后 nums = [2,3]
 * - 移出 2 和 3 ，之后 nums = []
 * 不再有和为 5 的数对，因此最多执行 2 次操作。
 * 示例 2：
 *
 * 输入：nums = [3,1,3,4,3], k =  6
 * 输出：1
 * 解释：开始时 nums = [3,1,3,4,3]：
 * - 移出前两个 3 ，之后nums = [1,4,3]
 * 不再有和为 6 的数对，因此最多执行 1 次操作。
 *
 * 暴力n*n
 * 排序后双指针
 * 和大于k  小的数+1
 * 和小于k  大的数-1
 * 等于k 各+ -
 **/
public class K和数对的最大数目 {
    public static int maxOperations(int[] nums, int k) {

        // 1. 先对数组进行排序
        Arrays.sort(nums);

        int result = 0;

        // 2. 定义双指针i和j,分别指向数组首尾
        int i = 0, j = nums.length-1;

        int sum = 0;

        // 3. 当i和j未相遇时循环
        while(i<j){

            // 4. 计算两数之和
            sum = nums[i] + nums[j];

            // 5. 如果两数之和等于k,结果+1
            if(sum == k){
                ++result;

                // 并移动指针接着找下一组
                ++i;
                --j;

                // 6. 如果大于k,右指针左移找更小的数
            } else if(sum>k){
                --j;

                // 7. 如果小于k,左指针右移找更大的数
            } else {
                ++i;
            }
        }

        // 8. 返回结果
        return result;
    }
}
